Field of the Invention
The invention relates to a method for optimizing an area of a ternary FPRM circuit, particularly to a method for optimizing an area of a ternary FPRM circuit using population migration algorithm.
Description of the Related Art
Any ternary (also known as three-valued) logic function can be represented by Boolean logic and Reed-Muller (RM) logic. Compared with traditional Boolean logic, communication circuits, parity checking circuits and operation circuits and the like based on RM logic have more compact structures and better testability. A RM logic function usually takes two forms of expression: fixed-polarity (Fixed-polarity Reed-Muller, FPRM) and mixed-polarity (Mixed-polarity Reed-Muller, MPRM). For a ternary FPRM logic function which has n variables, there are 3n fixed polarities which correspond to 3n different ternary FPRM expressions. Whether a ternary FPRM expression is simple or not is determined by its corresponding polarities. In turn, the complexity of the ternary FPRM expression directly determines the performance indices of the ternary FPRM circuit, such as area and power consumption. As a result, the polarities of a ternary FPRM circuit significantly impact the performance indices, such as area and power consumption, of the ternary FPRM circuit.
So far, a method for optimizing an area of a ternary FPRM circuit principally realizes area optimization by searching an optimal polarity. For area optimization of a small-scale ternary FPRM circuit, generally, an exhaustive method is used to traverse each polarity of a RM logic function representing the ternary FPRM circuit to search for the optimal polarity. For area optimization of a large-scale ternary FPRM circuit, search space is greatly increased due to an exponential relationship between variables and polarities, and it is quite difficult for an exhaustive method to obtain optimal results within limited time. Therefore, there is a need to find an efficient and intelligent algorithm to improve search efficiency, in order to get the optimal polarity for a ternary FPRM circuit as quickly as possible, and to achieve area optimization of the ternary FPRM circuit. Studies show that, for area optimization of a large-scale ternary FPRM circuit, a whole annealing genetic algorithm is employed to search the area-optimal polarity to obtain the smallest area of the circuit; however, there is still room for improvement in polarity search results, and it is difficult to find the optimal polarity.
Population Migration Algorithm (PMA) is a new global optimization search algorithm, proposed by Chinese scholar Zhou Yonghua, et al. according to the laws of population migration. PMA principally simulates the mechanism that people migrate along with economic center and disperse as population pressure increases. Population migration algorithm is a probabilistic search algorithm, which implements global parallel search and continuously focuses on the space that may contain the optimal solution to search for the optimal or proximate-optimal solution. Population migration algorithm is simple in principle and easy to operate, and compared with the whole annealing genetic algorithm, it significantly improves optimization effect for some functions, and has strong convergence and global optimization searching ability.
In view of this, there is provided a method for optimizing an area of a ternary FPRM circuit using population migration algorithm.